package hot100;


/*
 * Author：江松
 * Date：2023/4/7 11:19
 *
 二叉树的序列化与反序列化：
前序序列化：注意多位数，负数，空值
长度+num+判断符号

前序生成
 */

public class Main297 {
    class TreeNode {
        int val = 0;
        TreeNode left ;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    StringBuilder sb=new StringBuilder();
    int i=0;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null){
            sb.append('#');
            return sb.toString();
        }
        int val=root.val;
        boolean flag=true;
        if(val<0){
            val=-val;
            flag=false;
        }
        int t=val;
        int bit=val==0?1:0;
        while(t!=0){
            t/=10;
            bit++;
        }

        sb.append(bit);
        sb.append(val);
        if(!flag)sb.append('-');

        serialize(root.left);
        serialize(root.right);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(i==data.length())return null;
        if(data.charAt(i)=='#'){
            i++;
            return null;
        }

        int bit=data.charAt(i++)-'0';
        int v=0;
        while(bit-->0){
            v=v*10+data.charAt(i++)-'0';
        }
        if(data.charAt(i)=='-'){
            v=-v;
            i++;
        }

        TreeNode root=new TreeNode(v);
        root.left=deserialize(data);
        root.right=deserialize(data);
        return root;
    }
}
